package algorithm.dynamic_programming;


public class RobotWalk {

    //动态规划通过空间换时间，将重复解不暴力递归去重复做，所以替换成结构化的缓存数据，以后遇到同样的子问题的时候直接拿答案
    //暴力递归（尝试） -->  记忆化搜索 -------------------------------->  经典的动态规划（细粒度的组织，严格的表结构）
    //                   （建立空间感，来观察有下一步优化的可能(斜率优化)（如果是枚举行为即求每一个格子的时候有for循环），CoinsWay
    //                   没有枚举行为即填表的时候只依赖有限的位置（记忆化搜索和严格表结构的方法一样的好））
    //记忆化搜索相当于在填表，只不过它只会填写实际存在的情况

    public static int ways1(int N, int M, int K, int P){
        if(N < 2 || M > N || P > N || M < 1 || P < 1)
            return 0;
        int walk = walk(N, M, K, P);
        return walk;
    }

    public static int walk(int N, int cur, int rest, int P){
        if(rest == 0){
            return cur == P? 1 : 0;
        }

        int res = 0;
        if(cur == N){
            res = walk(N, N - 1, rest - 1, P);
        }
        if(cur == 1){
            res = walk(N, cur + 1, rest - 1, P);
        }
        if(cur != N && cur != 1){
            int walk1 = walk(N, cur + 1, rest - 1, P);
            int walk2 = walk(N, cur - 1, rest - 1, P);
            res = walk1 + walk2;
        }
        return res;
    }

    public static int ways2(int N, int M, int K, int P){
        if(N < 2 || M > N || P > N || M < 1 || P < 1)
            return 0;

        int[][] dp = new int[N + 1][K + 1];
        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < K + 1; j++) {
                dp[i][j] = -1;
            }
        }
        int walk2 = walk2(N, M, K, P, dp);
        return walk2;
    }

    public static int walk2(int N, int cur, int rest, int P, int[][] dp){
        if(rest == 0){
            dp[cur][rest] = cur == P? 1 : 0;
            return dp[cur][rest];
        }
        if(dp[cur][rest] != -1)
            return dp[cur][rest];

        int res = 0;
        if(cur == N){
            res = walk2(N, N - 1, rest - 1, P, dp);
        }
        if(cur == 1){
            res = walk2(N, cur + 1, rest - 1, P, dp);
        }
        if(cur != N && cur != 1){
            int walk1 = walk2(N, cur + 1, rest - 1, P, dp);
            int walk2 = walk2(N, cur - 1, rest - 1, P, dp);
            res = walk1 + walk2;
        }
        dp[cur][rest] = res;
        return res;
    }

    public static int ways3(int N, int M, int K, int P){
        if(N < 2 || M > N || P > N || M < 1 || P < 1)
            return 0;
        int[][] dp = new int[N + 1][K + 1];
        dp[P][0] = 1;
        for (int j = 1; j <= K; j++) {
            for (int i = 1; i <= N; i++) {
                if(i == N){
                    dp[i][j] = dp[i-1][j-1];
                }
                if(i == 1){
                    dp[i][j] = dp[2][j-1];
                }
                if(i != N && i != 1){
                    dp[i][j] = dp[i + 1][j - 1] + dp[i - 1][j - 1];
                }
            }
        }
        return dp[M][K];
    }



    public static void main(String[] args) {
        System.out.println(ways1(7, 4, 9, 5));
        System.out.println(ways2(7, 4, 9, 5));
        System.out.println(ways3(7, 4, 9, 5));
    }
}
